List of NP-complete problems
Here are some of the more commonly known problems that are NP-complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP-complete problems). Most of the problems in this list are taken from Garey and Johnson's seminal book Computers and Intractability: A Guide to the Theory of NP-Completeness, and are here presented in the same order and organization.
-
Graph theory
Covering and partitioning
-
- NP-complete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. NP-complete variants include the connected dominating set problem.
-
- This is the same problem as coloring the complement of the given graph.[6]
-
- NP-complete special cases include the minimum maximal matching problem,[13] which is essentially equal to the edge dominating set problem (see above).
Subgraphs and supergraphs
Vertex ordering
Iso- and other morphisms
Miscellaneous
Network design
Spanning trees
Cuts and connectivity
- Graph partitioning
- Acyclic partition
- Maximum cut[1]
- Minimum bounded cut (minimum cut into bounded sets)
- Biconnectivity augmentation
- Strong connectivity augmentation
- Network reliability
- Network survivability
- Normalized cut[68]
- Multiway cut
- Minimum k-cut
- k-vital edges
Routing problems
Flow problems
- Minimum edge-cost flow
- Integral flow with multipliers
- Path constrained network flow
- Integral flow with homologous arcs
- Integral flow with bundles
- Undirected flow with lower bounds
- Directed two-commodity integral flow
- Undirected two-commodity integral flow
- Disjoint connecting paths
- Maximum length-bounded disjoint paths
- Maximum fixed-length disjoint paths
- Maximum flow network interdiction problem
- Unsplittable multicommodity flow
Miscellaneous
Graph Drawing
Graphs occur frequently in everyday applications, and are used to model a lot of often huge data. Such examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (see e.g. Facebook or LinkedIn). Therefore, even when all information is available in the form of a graph, it is important to have good ways of visualizing the data in order to make sense of it and extract interesting features, and this is what makes graph drawing important.
- Rectilinear planarity testing[69]
- Upward planarity testing[69]
- Upward sphericity testing
- Maximum upward planar subgraph computation for embedded digraphs
Sets and partitions
Covering, hitting, and splitting
Weighted set problems
Set partitions
Storage and retrieval
Data storage
- Bin packing[81]
- Dynamic storage allocation[82]
- Pruned trie space minimization[83]
- Expected retrieval cost[84]
- Rooted tree storage assignment[85]
- Multiple copy file allocation[86]
- Capacity assignment[87]
Compression and representation
Database problems
Sequencing and scheduling
Sequencing on one processor
- Job sequencing[1]
- Sequencing with release times and deadlines
- Sequencing to minimize tardy tasks
- Sequencing to minimize tardy weight
- Sequencing to minimize weighted completion time
- Sequencing to minimize weighted tardiness
- Sequencing with deadlines and set-up times
- Sequencing to minimize maximum cumulative cost
Multiprocessor scheduling
- Multiprocessor scheduling
- Precedence constrained scheduling
- Resource constrained scheduling
- Scheduling with individual deadlines
- Preemptive scheduling
- Scheduling to minimize weighted completion time
Shop scheduling
Miscellaneous
Mathematical programming
Algebra and number theory
Divisibility problems
Solvability of equations
Miscellaneous
Games and puzzles
Logic
Propositional logic
Propositional logic problems, in particular satisfiability problems and their variants, are of particular practical interest because many practical problems can be solved by expressing them as satisfiability problems, and then using efficient SAT solvers to obtain an exact solution quickly.
Miscellaneous
Automata and language theory
Automata theory
- Reduction of incompletely specified automata[133]
- Minimum inferred finite state automaton[134]
Formal languages
- Testing whether a tree may be represented as Euclidean minimum spanning tree
- Unit disk graph recognition (Unit disk graphs are intersection graphs of circles of unit radius in the plane)[140]
- Many motion planning among polygonal obstacles in the plane are NP-hard.
- Planar partitioning into connected subassemblies: Given a set A of non-overlapping (but possibly touching) polygons in the plane, decide if there is a proper subset S of A that can be separated from A\S by a collision-free rigid motion of S, and such that both S and A\S are connected.[141]
- Art gallery problem and its variations.
Program optimization
Code generation
- Register sufficiency
- Feasible register assignment
- Register sufficiency for loops
- Code generation on a one-register machine
- Code generation with unlimited registers
- Code generation for parallel assignments
- Code generation with address expressions
- Code generation with unfixed variable locations
- Ensemble computation
- Microcode bit optimization
Programs and schemes
- Inequivalence of programs with arrays
- Inequivalence of programs with assignments
- Inequivalence of finite memory programs
- Inequivalence of loop programs without nesting
- Inequivalence of simple functions
- Strong inequivalence of Ianov schemes
- Strong inequivalence for monadic recursion
- Non-containment for free B-schemes
- Non-freedom for loop-free program schemes
- Programs with formally recursive procedures
Miscellaneous
See also
Notes
- ^ a b c d e f g h i j k l m n o p q r s t u Karp (1972)
- ^ Garey & Johnson (1979): GT1
- ^ Garey & Johnson (1979): GT2
- ^ Garey & Johnson (1979): GT3
- ^ Garey & Johnson (1979): GT4
- ^ Garey & Johnson (1979): GT15
- ^ Garey & Johnson (1979): GT5
- ^ Garey & Johnson (1979): GT6
- ^ Garey & Johnson (1979): GT7
- ^ Garey & Johnson (1979): GT8
- ^ Garey & Johnson (1979): GT9
- ^ Minimum Independent Dominating Set
- ^ Garey & Johnson (1979): GT10
- ^ Garey & Johnson (1979): GT11
- ^ Garey & Johnson (1979): GT12
- ^ Garey & Johnson (1979): GT13
- ^ Garey & Johnson (1979): GT14
- ^ Garey & Johnson (1979): GT16
- ^ Garey & Johnson (1979): GT17
- ^ Garey & Johnson (1979): GT18
- ^ a b Garey & Johnson (1979): GT56
- ^ a b Arnborg, Corneil & Proskurowski (1987)
- ^ Garey & Johnson (1979): GT19
- ^ Garey & Johnson (1979): GT20
- ^ Garey & Johnson (1979): GT23
- ^ Garey & Johnson (1979): GT24
- ^ Garey & Johnson (1979): GT25
- ^ Garey & Johnson (1979): GT26
- ^ Garey & Johnson (1979): GT27
- ^ Garey & Johnson (1979): GT28
- ^ Garey & Johnson (1979): GT29
- ^ Garey & Johnson (1979): GT30
- ^ Garey & Johnson (1979): GT31
- ^ Garey & Johnson (1979): GT32
- ^ Garey & Johnson (1979): GT33
- ^ Garey & Johnson (1979): GT34
- ^ Garey & Johnson (1979): GT35
- ^ Garey & Johnson (1979): GT36
- ^ Garey & Johnson (1979): GT37
- ^ Garey & Johnson (1979): GT38
- ^ Garey & Johnson (1979): GT39
- ^ Garey & Johnson (1979): GT40
- ^ Garey & Johnson (1979): GT41
- ^ Garey & Johnson (1979): GT42
- ^ Garey & Johnson (1979): GT43
- ^ Garey & Johnson (1979): GT44
- ^ Garey & Johnson (1979): GT45
- ^ Garey & Johnson (1979): GT46
- ^ Garey & Johnson (1979): GT47
- ^ Kashiwabara & Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981).
- ^ Garey & Johnson (1979): GT48
- ^ Garey & Johnson (1979): GT49
- ^ Garey & Johnson (1979): GT50
- ^ Garey & Johnson (1979): GT51
- ^ Garey & Johnson (1979): GT52
- ^ Garey & Johnson (1979): GT53
- ^ Garey & Johnson (1979): GT54
- ^ Garey & Johnson (1979): GT55
- ^ Garey & Johnson (1979): GT57
- ^ Garey & Johnson (1979): GT58
- ^ Garey & Johnson (1979): GT59
- ^ Garey & Johnson (1979): GT60
- ^ Garey & Johnson (1979): GT61
- ^ Garey & Johnson (1979): GT62
- ^ Garey & Johnson (1979): GT63
- ^ Garey & Johnson (1979): GT64
- ^ Garey & Johnson (1979): GT65
- ^ "Normalized Cuts and Image Segmentation". IEEE. 20 October 2009. http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf.
- ^ a b "On the computational complexity of upward and rectilinear planarity testing". Lecture Notes in Computer Science. 894/1995. 1995. pp. 286–297. doi:10.1007/3-540-58950-3_384.
- ^ Garey & Johnson (1979): SP1
- ^ Garey & Johnson (1979): SP2
- ^ Garey & Johnson (1979): SP3
- ^ Garey & Johnson (1979): SP4
- ^ Garey & Johnson (1979): SP5
- ^ Garey & Johnson (1979): SP6
- ^ Garey & Johnson (1979): SP7
- ^ Garey & Johnson (1979): SP8
- ^ Garey & Johnson (1979): SP9
- ^ Garey & Johnson (1979): SP10
- ^ Garey & Johnson (1979): SP11
- ^ Garey & Johnson (1979): SR1
- ^ Garey & Johnson (1979): SR2
- ^ Garey & Johnson (1979): SR3
- ^ Garey & Johnson (1979): SR4
- ^ Garey & Johnson (1979): SR5
- ^ Garey & Johnson (1979): SR6
- ^ Garey & Johnson (1979): SR7
- ^ Garey & Johnson (1979): SR8
- ^ Garey & Johnson (1979): SR9
- ^ Garey & Johnson (1979): SR10
- ^ Garey & Johnson (1979): SR11
- ^ Garey & Johnson (1979): SR12
- ^ Garey & Johnson (1979): SR13
- ^ Garey & Johnson (1979): SR14
- ^ Garey & Johnson (1979): SR15
- ^ Garey & Johnson (1979): SR16
- ^ Garey & Johnson (1979): SR17
- ^ Garey & Johnson (1979): SR18
- ^ Garey & Johnson (1979): SR19
- ^ Garey & Johnson (1979): SR20
- ^ Garey & Johnson (1979): SR21
- ^ Garey & Johnson (1979): SR22
- ^ Garey & Johnson (1979): SR23
- ^ Garey & Johnson (1979): SR24
- ^ Garey & Johnson (1979): SR25
- ^ Garey & Johnson (1979): SR26
- ^ Garey & Johnson (1979): SR27
- ^ Garey & Johnson (1979): SR28
- ^ Garey & Johnson (1979): SR29
- ^ Garey & Johnson (1979): SR30
- ^ Garey & Johnson (1979): SR31
- ^ Garey & Johnson (1979): SR32
- ^ Garey & Johnson (1979): SR33
- ^ Garey & Johnson (1979): SR34
- ^ Garey & Johnson (1979): SR35
- ^ Garey & Johnson (1979): SR36
- ^ http://www.cs.rpi.edu/~civria/max-vol-inapprox.pdf
- ^ Yato, Takauki (2003). "Complexity and Completeness of Finding Another Solution and its Application to Puzzles". http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.8380&rep=rep1&type=pdf.
- ^ R. Clifford, M. Jalsenius, A. Montanaro and B. Sach (2010-08-19). The Complexity of Flood Filling Games. arXiv:1001.4420.
- ^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.
- ^ Holzer & Ruepp (2007)
- ^ Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs". http://dimacs.rutgers.edu/~graham/pubs/papers/cormodelemmings.pdf.
- ^ Kaye (2000)
- ^ Garey & Johnson (1979): LO1
- ^ Garey & Johnson (1979): LO2
- ^ Garey & Johnson (1979): LO3
- ^ Garey & Johnson (1979): LO4
- ^ Garey & Johnson (1979): LO5
- ^ Garey & Johnson (1979): LO6
- ^ Garey & Johnson (1979): LO8
- ^ Garey & Johnson (1979): LO9
- ^ Garey & Johnson (1979): LO10
- ^ Garey & Johnson (1979): AL7
- ^ Garey & Johnson (1979): AL8
- ^ Garey & Johnson (1979): AL10
- ^ Garey & Johnson (1979): AL11
- ^ Garey & Johnson (1979): AL15
- ^ Garey & Johnson (1979): AL17
- ^ Garey & Johnson (1979): AL18
- ^ H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3–24, 1998
- ^ "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.
- ^ Barry A. Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.
References
- Cook, S.A. (1971). "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151–158. doi:10.1145/800157.805047.
- Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W.. Complexity of Computer Computations. Plenum. pp. 85–103.
- Dunne, P.E.. "An annotated list of selected NP-complete problems". COMP202, Dept. of Computer Science, University of Liverpool. http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html. Retrieved 2008-06-21.
- Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH NADA, Stockholm. http://www.nada.kth.se/~viggo/problemlist/compendium.html. Retrieved 2008-06-21.
- Dahlke, K. "NP-complete problems". Math Reference Project. http://www.mathreference.com/lan-cx-np,intro.html. Retrieved 2008-06-21.
- Friedman, E (2002). "Pearl puzzles are NP-complete". Stetson University, DeLand, Florida. http://www.stetson.edu/~efriedma/papers/pearl/pearl.html. Retrieved 2008-06-21.
- Holzer, Markus; Ruepp, Oliver (2007). "The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake". Proceedings, 4th International Conference on Fun with Algorithms, LNCS 4475. Springer, Berlin/Heidelberg. pp. 198–212. doi:10.1007/978-3-540-72914-3_18. ISBN 978-3-540-72913-6.
- Kaye, Richard (2000). "Minesweeper is NP-complete". Mathematical Intelligencer 22 (2): 9–15. doi:10.1007/BF03025367. Further information available online at Richard Kaye's Minesweeper pages.
- Kashiwabara, T.; Fujisawa, T. (1979). "NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph". Proc. International Symposium on Circuits and Systems. pp. 657–660 .
- Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). "One-dimensional logic gate assignment and interval graphs". IEEE Transactions on Circuits and Systems 26 (9): 675–684. doi:10.1109/TCS.1979.1084695 .
- Lengauer, Thomas (1981). "Black-white pebbles and graph separation". Acta Informatica 16 (4): 465–475. doi:10.1007/BF00264496 .
- Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej (1987). "Complexity of finding embeddings in a $k$-tree". SIAM Journal on Algebraic and Discrete Methods 8 (2): 277–284. doi:10.1137/0608024 .
- Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs". Proceedings of Third International Conference on Fun with Algorithms (FUN 2004). pp. 65-76.